package com.study.algorithm.sort;

import java.text.MessageFormat;
import java.util.Arrays;

/**
 * 归并排序
 *
 * @author YangGuGu
 */
public class Merge implements Sort {

  private Merge() {
  }

  private static class Holder {
    private static final Merge INSTANCE = new Merge();
  }

  public static Merge getInstance() {
    return Merge.Holder.INSTANCE;
  }

  /**
   * 辅助数组
   */
  private static Comparable[] assist;

  @Override
  public void sort(Comparable[] source) {
    if (source == null || source.length == 0) {
      return;
    }
    System.out.println("待排序数组：" + Arrays.toString(source));
    sort(source, 0, source.length - 1);
    System.out.println("排好序数组：" + Arrays.toString(source));
  }

  private void sort(Comparable[] source, int left, int right) {
    if (left >= right) {
      return;
    }
    System.out.println(
        MessageFormat.format("本次排序数组：{0}，最左元素下标：{1}，最右元素下标：{2}"
            , Arrays.toString(source), left, right)
    );
    int middle = calculateMiddleIndex(left, right);
    // 递归排序左半部分
    sort(source, left, middle);
    // 递归排序右半部分
    sort(source, middle + 1, right);
    // 左半部分和右半部分归并
    merge(source, left, middle, right);
  }

  private void merge(Comparable[] source, int left, int middle, int right) {
    System.out.println(
        MessageFormat.format("开始合并数组：{0}，最左元素下标：{1}，中间元素下标：{2}，最右元素下标：{3}"
            , Arrays.toString(source), left, middle, right)
    );

    assist = new Comparable[right - left + 1];
    int assistIndex = 0;

    int leftPointer = left;
    int rightPointer = middle + 1;

    while (leftPointer <= middle && rightPointer <= right) {
      // 左半部分指针下标元素比右半部分指针下标元素大，交换然后左半部分指针后移一位
      if (SortHelper.getInstance().greater(source[leftPointer], source[rightPointer])) {
        assist[assistIndex++] = source[rightPointer++];
      } else {
        assist[assistIndex++] = source[leftPointer++];
      }
    }

    for (int i = leftPointer; i <= middle; i++) {
      assist[assistIndex++] = source[i];
    }

    for (int i = rightPointer; i <= right; i++) {
      assist[assistIndex++] = source[i];
    }

    for (int i = left; i <= right; i++) {
      source[i] = assist[i - left];
    }
  }

  private int calculateMiddleIndex(int left, int right) {
    // 可能会超过int最大范围：int middle = right + left / 2;
    return left + (right - left) / 2;
  }
}
